\documentclass{llncs}

\usepackage[utf8]{inputenc}
\usepackage[brazil]{babel}

\usepackage{proof}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}

\sloppy

\begin{document}

\title{Predição Dinâmica de Quantidade de Iterações em Laços}

\author{Péricles Rafael Oliveira Alves, Douglas do Couto Teixeira, \\
Fernando Magno Quintão Pereira}

\institute{Departamento de Ciência da Computação -- UFMG -- Brasil
\email{\{periclesrafael,douglas,fernando\}@dcc.ufmg.br}
}


\maketitle

%mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm
\begin{abstract}
A compilação just-in-time é um dos mecanismos mais efetivos que linguagens
virtualizadas possuem para prover aos seus usuários alto desempenho.
Essa tecnologia permite que um programa seja compilado para código nativo
enquanto ele é interpretado.
Um dos grandes desafios relacionados à compilação just-in-time é descobrir
o melhor momento para invocar o compilador.
Se a invocação ocorre muito cedo, é maior a chance de que o tempo de execução
do programa não seja grande o suficiente para amortizar o custo da compilação.
Por outro lado, uma invocação tardia pode fazer com que código crítico seja
interpretado durante um tempo muito longo.
O objetivo deste artigo é descrever uma heurística que determina,
dinamicamente, quais programas tendem a executar durante longo tempo.
A heurística que propomos é de extraordinária simplicidade: antes de
interpretarmos a execução de um laço, nós verificamos os valores usados em
sua condição de término.
Temos acesso a tais valores, uma vez que estamos gerando código para um
programa durante a sua interpretação.
Não obstante sua simplicidade, nossa heurística é surpreendentemente precisa:
resultados empíricos obtidos sobre uma vasta coleção de programas JavaScript,
demonstram uma taxa de acerto de mais de 60\%.
Nós implementamos essa heurística no navegador Firefox, e fomos capazes de
aumentar o desempenho de benchmarks conhecidos em até 91\%.
Essa mesma técnica possui precisão similar em linguagens estaticamente
compiladas.
Instrumentação inserida via LLVM nos permitiu prever, com uma taxa de acerto
por volta de 60\%, a quantidade exata de iterações dos laços
encontrados nos programas C disponíveis em SPEC CPU 2006.
\end{abstract}

%mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm
\section{Introdução}
\label{sec:int}

Linguagens de programação interpretadas desfrutam de grande popularidade entre
os desenvolvedores de software.
Prova dessa afirmação é o grande apelo que Java, JavaScript, Python e
C\# exercem sobre a indústria e sobre a academia.
Dentre as vantagens de ambientes de execução virtualizados, isto é, baseados
na interpretação de programas, destaca-se a portabilidade.
Essa portabilidade transformou JavaScript na representação intermediária
comumente usada pelo lado cliente de aplicações web.
Não somente a maior parte desses programas são desenvolvidos diretamente em
JavaScript, como também essa mesma linguagem é usada como alvo de arcabouços
tais como o Google Web
Toolkit~\footnote{\texttt{https://developers.google.com/web-toolkit/}} e o
Emscripten da Mozilla~\footnote{\texttt{www.mozilla.org/en-US/research/projects}}.
Entretanto, essa portabilidade tem seu preço: a interpretação de programas
tende a ser mais lenta que a sua execução direta.

A compilação just-in-time é uma tecnologia chave para reduzir essa distância
entre linguagens virtualizadas e nativamente executadas.
Existem compiladores just-in-time como o V8, usado no navegador
Chrome, que compilam programas imediatamente antes deles serem executados.
Porém, tradicionalmente, um compilador just-in-time produz código nativo para
um programa enquanto ele está sendo interpretado.
A definição de quando compilar um programa, contudo, é um problema difícil,
e até hoje não resolvido satisfatoriamente~\cite{Lucas13}.
A compilação prematura pode forçar a geração de código nativo para
programas que não executam durante tempo suficiente para
amortizar o custo imposto pelo compilador.
Por outro lado, a compilação tardia pode fazer com que código crítico execute
durante um tempo desnecessariamente longo.
Caso interpretadores fossem dotados de algum tipo de clarividência, eles
poderiam invocar o compilador just-in-time mais adequado para um programa com
base em seu tempo de execução.
Programas que executassem durante um tempo muito curto seriam somente
interpretados, e programas que executassem durante muito tempo seriam
compilados com um nível alto de otimizações.
Poderíamos até mesmo envisionar um degradê no qual mais ou menos otimizações
fossem aplicadas sobre um programa com base em seu tempo predito de
execução.
O objetivo desse artigo é armar o interpretador com uma versão aproximada
dessa capacidade de predição.

Este artigo descreve uma heurística que prevê, dinamicamente,
a quantidade de iterações de um laço.
Em outras palavras, buscamos determinar quantas vezes a condição de um
laço será avaliada, imediatamente antes de iniciarmos a execução desse
código.
A fim de alcançar tal objetivo, descreveremos e analisaremos experimentalmente
uma heurística muito simples.
Laços, como por exemplo \texttt{for (int i = 0; i < N; i++);} são
guardados por uma condição de parada.
Em nosso exemplo, \texttt{i < N}.
Dificilmente o valor de todas essas variáveis pode ser estimado precisamente
de maneira estática.
Entretanto, durante a interpretação do programa temos acesso direto a tais
valores.
Nossa heurística consiste em verificar a condição de parada, mais o valor
das variáveis usadas nesse teste, e com base em tal leitura, determinar,
a priori, o número de iterações do laço.
Em nosso exemplo, iríamos prever que o laço executaria por
\texttt{val(N) - 0} iterações, sendo \texttt{val(N)} o valor da variável
\texttt{N} em tempo de execução.

Existem diversos fatores que podem levar-nos a predições erradas.
Por exemplo, o laço pode ser interrompido prematuramente, ou ele pode
conter outros comandos que alterem a sua variável de indução, \texttt{i} em
nosso exemplo.
Ainda assim, uma avaliação empírica dessa heurística demonstra que ela é
muito precisa.
Para validar tal afirmação, nós a implementamos em {\em IonMonkey}, o
compilador just-in-time usado pelo Navegador Mozilla Firefox.
Nós utilizamos o navegador modificado para executar os programas JavaScript
encontrados nas 100 páginas mais visitadas, de acordo com o índice
Alexa~\footnote{\texttt{www.alexa.com}}.
Nossa máquina experimental analisou um total de 1441 laços.
Fomos capazes de prever, exatamente, a execução de 928 laços, e fomos capazes
de prever 986 laços com uma margem de erro relativamente pequena.
Nossa técnica pode ser usada também sobre programas compilados
estaticamente.
A fim de demonstrar tal afirmação, nós modificamos o compilador
LLVM~\cite{Lattner04} para gerar código instrumentado.
Essa instrumentação lê os valores de controle de laços, e também recorda o
número de execuções de tais iteradores.
Os resultados obtidos são também muito precisos.
Os laços instrumentados foram visitados cerca de 250 milhões de vezes, e
pudemos prever corretamente o número de iterações da maior parte deles.

Concluímos este trabalho demonstrando que nossa técnica pode ser efetivamente
usada para aumentar o desempenho de ambientes de execução de qualidade
industrial.
Testamos uma versão modificada do Firefox em três diferentes, e igualmente
conhecidos, benchmarks: {\em V8}, {\em SunSpider} e {\em Kraken}.
Pudemos obter speedups em todos eles.
Em SunSpider, por exemplo, registramos um aumento médio de eficiência de 10\%.
Embora esse número seja modesto, lembramos que estamos testando nossa
idéia em uma das mais eficientes máquinas virtuais disponíveis publicamente.
Além disso, nas palavras de Robert Hundt, diretor da equipe de compiladores
da empresa Google, ``At the scale of datacenters, every single performance
percent matters! A single percent improvement can mean millions of dollars from
more program features or improved utilization."~\footnote{\texttt{http://homepages.dcc.ufmg.br/~fernando/classes/dcc888/ementa/slides/
Introduction.pdf}}

%mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm
\section{Predição de Código Quente}
\label{sec:bkg}

% Introducing the example:
O objetivo desta seção é descrever o que é {\em predição de código quente}, e
mostrar porque essa técnica é fundamental para aumentar o desempenho de
ambientes de programação virtualizados.
Com tal propósito, usaremos o programa visto na figura~\ref{fig:countFreq}.
Esse programa conta a frequência de cada letra presente em um arquivo de
texto.
A função \texttt{countFreq} lê um arquivo, e para cada uma de suas linhas,
invoca a rotina \texttt{countLine}.
Esse procedimento atravessa a linha que ele recebe como argumento, chamando
a função \texttt{storeFreq} sobre cada caractere encontrado.
Note que a complexidade assimptótica do laço em \texttt{countFreq} é
proporcional ao número de linhas do arquivo lido, e a complexidade do laço em
\texttt{countLine} é proporcional ao número de caracteres na {\em string}
recebida.

\begin{figure}[t!]
\begin{center}
\includegraphics[width=0.9\columnwidth]{images/countFreq}
\caption{Um programa, escrito em JavaScript, que conta a frequência de
cada letra em um arquivo de texto.}
\label{fig:countFreq}
\end{center}
\end{figure}

% Interpretation vs compilation
Em um ambiente de execução virtualizado, como o que é normalmente adotado por
navegadores ao executar arquivos JavaScript, um programa pode ser interpretado
ou traduzido para linguagem nativa.
O custo de interpretar um comando, isto é, uma instrução de baixo nível, é mais
alto que o custo de executar essa instrução diretamente na máquina alvo.
Tal preço deve-se à grande quantidade de intermediários entre o interpretador
e o {\em hardware} subjacente.
Por outro lado, embora a execução de código nativo seja mais barata que a
interpretação de instruções, a sua geração envolve um custo alto.
Antes de poder ser executado diretamente, o programa JavaScript precisa ser
traduzido para linguagem de máquina.
A esse processo de tradução dá-se o nome de {\em compilação Just-in-Time}.

% Hot vs cold code.
Em sua dissertação de mestrado~\cite{Lucas13}, Divino César explicou, com
grande riqueza de detalhes, que o problema de definir qual código interpretar
ou compilar é de difícil resolução.
Programas que vão ser utilizados por um longo tempo deveriam ser compilados.
Tais programas são comumente chamados {\em quentes}.
Programas que executam por curto período deveriam ser interpretados.
Por conseguinte, esses programas são chamados {\em frios}.
Naturalmente, o problema de determinar por quanto tempo um programa irá ser
executado, isto é, se aquele programa é código quente ou frio, é indecidível.
Por exemplo, se a função \texttt{countFreq} na figura~\ref{fig:countFreq} for
alimentada com arquivos que contêm muitas linhas de código, então ela deveria
ser traduzida para código nativo, pois executará durante muito tempo.
Contudo, se os arquivos de entrada possuírem poucas linhas, então a velocidade
extra do código nativo pode não ser suficiente para amortizar o custo de sua
geração.
Raciocínio análogo aplica-se à função \texttt{countLine}, porém, uma vez que
essa função é invocada dentro de um laço, a partir da função \texttt{countFreq},
o seu custo de execução total envolve a soma de cada invocação.
E mesmo funções que não possuem laços podem ser quentes.
Em nosso exemplo, a função \texttt{storeFreq} é invocada uma vez para cada
caractere no arquivo de entrada.

O problema de determinar a melhor forma de executar código torna-se ainda mais
difícil quando percebemos que ambientes de execução virtual podem dispor de mais
de um nível de compilação.
Por exemplo, o Firefox, navegador que usamos nos experimentos apresentados
neste trabalho, dispõe de três modos de execução.
O primeiro realiza somente a interpretação pura de instruções escritas em uma
linguagem intermediária, usualmente chamada de {\em linguagem de bytecodes}.
O segundo modo realiza uma tradução direta, isto é, sem otimizações, de
{\em bytecodes} para código nativo.
Essa tradução insere também instrumentação de {\em profiling} no código gerado.
Finalmente, o terceiro modo de execução gera código nativo otimizado, usando,
para tal propósito, as informações coletadas tanto pelo interpretador quanto
pelo compilador base.
Essa última etapa de tradução possui um custo muito maior que a segunda, mas
produz código substancialmente mais eficiente.

\begin{figure}[t!]
\begin{center}
\includegraphics[width=0.9\columnwidth]{images/histogram}
\caption{Custo e ganho de diferentes modos de operação quando computados sobre a execução
de um programa JavaScript.}
\label{fig:histogram}
\end{center}
\end{figure}

O histograma na figura~\ref{fig:histogram} ilustra o custo e o ganho desses
diferentes modos de operação quando computados sobre a execução de uma
função.
O tempo total de execução dessa função é a área sob a curva mostrada, isto é,
sua integral.
Vemos que o tempo demandado para a interpretação dos bytecodes é maior que o
tempo exigido para a execução das instruções em código nativo.
Ainda nessa linha, o tempo de execução do código produzido pelo
compilador base é maior que o tempo de execução do mesmo código produzido
pelo compilador otimizante.
Entretanto, o tempo de processamento que esse segundo compilador exige é
substancialmente maior que o tempo de execução que aquele primeiro requer.
O problema que estamos interessados neste artigo é {\em como minimizar a
área sob a curva do histograma de execução de uma função}.

A predição de código quente consiste em determinar, de antemão, quais trechos
de código virtualizado serão executados por longo tempo.
A principal técnica usada atualmente é baseada em {\em limiares de
execução}~\cite{Bala00}.
Contadores são associados aos laços presentes no programa, sendo incrementados
a cada iteração.
Uma vez atingido um certo limiar, o ambiente de execução marca aquele
código como quente, e ele é passado ao compilador Just-in-Time.
A compilação, nesse caso, pode se dar à granularidade de funções, conforme
acontece no V8 da Google e no JaegerMonkey da Mozilla~\cite{Hackett12}.
Doutro modo, a compilação pode se dar à granularidade de caminhos dentro de
funções, como originalmente proposto por Bala {\em et al.}~\cite{Bala00} e
recentemente discutido por Gal {\em et al.}~\cite{Gal09}.
Neste trabalho nós estamos propondo uma abordagem complementar à técnica de
limiares de execução, a qual discutiremos na próxima seção.

%mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm
\section{Mecanismo de Predição Dinâmica}
\label{sec:sol}

Segundo Appel e Palsberg~\cite[p.376]{Appel02}, um laço é um conjunto de
nodos $S$ do grafo de fluxo de controle de um programa, includindo um
nodo cabeçalho $H$, com as seguintes três propriedades:

\begin{itemize}
\item a partir de qualquer nodo em $S$ existe um caminho que chega a $H$;
\item existe um caminho de $H$ até qualquer nodo que faz parte de $S$;
\item não existe caminho -- que não contenha $H$ -- de qualquer nodo fora de
$S$ para qualquer nodo em $S$.
\end{itemize}

Neste artigo um {\em Laço de Intervalo} é um laço cuja condição de controle
usa um dos seguintes operadores: $<$, $>$, $\leq$ ou $\geq$.
Esses laços são importantes para o nosso trabalho porque podemos aplicar a
nossa heurística sobre eles.
Laços que utilizam outras condições de controle, envolvendo testes de
igualdade, ou chamadas de funções que retornem valores booleanos, não são
passíveis de predição dinâmica segundo a nossa técnica.
Voltando ao exemplo da figura~\ref{fig:countFreq}, o laço na função
\texttt{countLine} é de intervalo, mas o laço em \texttt{countFreq} não o é.

A nossa heurística consiste em usar a diferença dos valores lidos pela
instrução de comparação como a previsão do número de iterações do laço.
Usamos a diferença simples, isto é, não consideramos passos maiores que um
no incremento de variáveis de indução.
Passos de tamanho quatro, por exemplo, são comuns em programas que percorrem
vetores inteiros em linguagens de máquina, mas não são comuns em
representações intermediárias de mais alto-nível.
O algoritmo da figura~\ref{fig:heuristics} efetua esse teste durante a
interpretação do programa.
A figura~\ref{fig:heuristics}(a) mostra um trecho de código de
{\em SpiderMonkey}, o interpretador usado pelo Firefox.
Os comandos vistos na parte (a) da figura são responsáveis pelo processamento
do predicado que controla o laço.
Na linha (8) nós separamos os testes de intervalo, e na linha (9) nós
invocamos a heurística sobre os testes válidos.

% Six versions:
%
% 1) First loop > baseline else Second loop > baseline
%
% 2) First loop > baseline or First loop > IonMonkey
%   else Second loop > baseline or Seoncd loop > IonMonkey
%
% *) Inline
%
% 4) Second loop > baseline
%
% 5) Second loop > baseline or Seoncd loop > IonMonkey
%
% *) Inline


\begin{figure}[t!]
\begin{center}
\includegraphics[width=1\columnwidth]{images/guess_hot}
\caption{Código de predição de número de iterações em laços.
(a) Interpretador SpiderMonkey.
(b) Nosso preditor.}
\label{fig:heuristics}
\end{center}
\end{figure}

O trecho de código que implementa a nossa heurística é visto na
figura~\ref{fig:heuristics}(b).
Nós analisamos no máximo um laço por execução do {\em script} no interpretador.
E, para cada laço analisado, levamos em consideração no máximo um
fator de aninhamento. Note que, caso o código otimizado produzido para um
{\em script} se torne inválido por algum motivo, o mesmo pode voltar a ser
executado pelo interpretador.
Dessa forma, é possível que analisemos mais de um laço por {\em script}.
Buscamos, assim, diminuir o custo que nossa técnica impõe sobre o
interpretador.
Durante a primeira visita feita a um laço, as condições nas linhas (2) e (3)
serão verdadeiras.
Na primeira visita feita a um laço aninhado, as condições nas linhas (2) e
(7) serão verdadeiras.
Se estivermos interpretando um {\em script} com múltiplos laços, somente 
tentaremos prever o número de iterações do primeiro deles.
Uma vez feita uma predição, o teste na linha (2) da figura~\ref{fig:heuristics}
passa a ser falso, e novas análises não são mais feitas até que o {\em script}
volte a ser interpretado, o que pode ocorrer devido àlguma
desotimização~\footnote{``desotimização" é o nome dado ao evento que ocorre
quando alguma suposição feita pelo interpretador ao gerar código se torna
falsa durante a execução do programa.}.
As figuras~\ref{fig:matrixMat}(a-c) mostram quais comparações nós analisamos em
um {\em scritp} que apresenta vários laços, e quais testes de nossa
heurística são executados em cada cabeçalho de laço.
Como se vê pela figura~\ref{fig:matrixMat}(c), analisamos um laço aninhado
somente se ele for o primeiro laço encontrado durante a interpretação do {\em script}. 

\begin{figure}[t!]
\begin{center}
\includegraphics[width=1\columnwidth]{images/matrixMat}
\caption{Exemplo de programas com múltiplos laços aninhados.
Nas figuras da esquerda analisamos somente os cabeçalhos em cinza.}
\label{fig:matrixMat}
\end{center}
\end{figure}

Dado um laço simples, controlado pela condição $op_1 < op_2$, nossa
heurística prevê que ele executará por $|op_2 - op_1|$ iterações, conforme
vemos na linha (5) da figura~\ref{fig:heuristics}.
Uma vez feita uma predição de número de iterações, esse valor fica armazenado
em \texttt{script.range}.
Por outro lado, caso estejamos em um laço aninhado, então nossa heurística
usa o produto das previsões feitas para os laços internos e externos como
a hipótese adotada para o número de iterações.
Esse cálculo é realizado na linha (9) da figura~\ref{fig:heuristics}(b).
Por exemplo, a figura~\ref{fig:matrixMat} mostra código que realiza a
multiplicação de duas matrizes, \texttt{a} e \texttt{b}.
Caso ambas as matrizes possuam 10 linhas e 10 colunas, então o laço mais
interno executará 1000 iterações, porém nós analisaremos somente os dois
laços mais externos, nas linhas (2) e (4) do exemplo.
Ao visitarmos o segundo desses laços, nossa heurística concluirá que ele
sofrerá \texttt{(a.height - i)} $\times$ \texttt{(b.width - j)} iterações.

Notamos que, sendo a nossa solução essencialmente heurística, estamos
sujeitos a predições errôneas.
Continuando com o exemplo da figura~\ref{fig:matrixMat}, se o limiar de
compilação fosse 101 iterações, o compilador just-in-time não seria
invocado imediatamente, ainda que o algoritmo de multiplicação matricial
viesse a iterar 1000 vezes.
Essa falha deve-se ao fato de analisarmos somente dois laços em uma cadeia de
aninhamento, o que excluí o terceiro laço, na linha (6) do exemplo, de nossa
predição.
Adotamos essa solução porque, em nosso entendimento, ela representa um bom
compromisso entre precisão e custo computacional.
Além disso, nossa heurística não exclui o método do contador tradicional
de limiar utilizado pelo interpretador: tendo o laço da linha (6) iterado pela
centésima primeira vez, o compilador JIT será automaticamente invocado.

\subsection{Políticas de Invocação do Compilador JIT}
\label{sub:pol}

A predição dinâmica de número de iterações em laços nos permite invocar o
compilador just-in-time mais cedo sobre código quente.
Contudo, a decisão de quando, e qual compilador invocar não é trivial.
A dificuldade vem do fato de termos a nossa disposição possivelmente
dois ou mais diferentes compiladores, por exemplo, um compilador {\em base} e
um compilador {\em otimizante}.
Além disso, podemos optar por substituir a chamada de funções pelo seu
corpo, uma otimização conhecida como {\em inlining}.
Cada um desses modos de compilação -- base, otimizante e inlining -- é
invocado depois de certos limiares.
Esses limiares dão margem a duas diferentes políticas de invocação.
A primeira delas, que chamaremos de {\em arrojada}, invoca um dos modos de
compilação se a predição na linha (5) da figura~\ref{fig:heuristics}, feita
para o primeiro laço encontrado, for maior que algum dos limiares.
A segunda política de invocação, que chamaremos de {\em prudente},
espera até que tenhamos iterado pelo laço mais externo pelo menos uma vez.
Assim, caso esse laço encapsule outro, podemos atingir o teste da linha
(7) da figura~\ref{fig:heuristics} com mais consistência.
A política arrojada tende a invocar o compilador base com mais frequência,
ao passo que a política prudente tende a invocar mais vezes os modos
avançados de compilação.

\subsection{Predição via Instrumentação}
\label{sub:inst}

A principal contribuição deste artigo é mostrar que o teste da
figura~\ref{fig:heuristics} é capaz de prever, com alta taxa de acerto, o
número de iterações em um laço.
Na seção~\ref{sec:exp} nós demostraremos esse fato para programas JavaScript
e para programas C.
A realização de tal experimento no ambiente de execução de JavaScript é
relativamente simples, pois basta alterarmos o interpretador dessa linguagem
para reportar a quantidade de iterações de cada laço.
Por outro lado, C não é uma linguagem interpretada.
A fim de coletar a quantidade de iterações dos laços encontrados em código
C, nós tivemos de instrumentar esses programas.

% TODO: pequeno bug na figura (c): "fprintf(inc)" deveria ser "fprintf(acc)".
\begin{figure}[t!]
\begin{center}
\includegraphics[width=1\columnwidth]{images/instrument}
\caption{Instrumentação de código usada para coletar o número de iterações
em laços presentes em código C.}
\label{fig:instrument}
\end{center}
\end{figure}

A figura~\ref{fig:instrument} ilustra como é feita tal instrumentação.
A parte (a) da figura mostra o programa C cujo laço queremos analisar
dinamicamente.
O grafo de fluxo de controle desse programa pode ser visto na parte (b) da
figura.
Em (c) vemos o programa modificado para coletar tanto a nossa previsão,
quanto o número real de iterações observadas durante a execução do programa.
Nossa instrumentação cria um novo cabeçalho para cada laço do programa.
Na figura em questão, o cabeçalho $L_1$ foi criado para o laço cuja
condição de parada encontra-se em $L_3$.
Esse novo cabeçalho contém um teste que, durante a primeira visita do
laço, imprime o número previsto de iterações.
Cada laço instrumentado contém um contador que guarda a quantidade de vezes
que ele itera.
Na figura, esse contador é a variável \texttt{acc}.
Nós inserimos código no pós-dominador de cada laço para imprimir o valor dessa
variável.
Um nodo $p$ pós-domina um nodo $q$, em um grafo direcionado com saída $s$, se
todo caminho de $q$ até $s$ necessariamente passa por $p$.
Em nosso exemplo, o pós-dominador do laço é o bloco $L_5$.

%mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm
\section{Resultados Experimentais}
\label{sec:exp}

Nós implementamos nossas idéias em {\em SpiderMonkey}, o interpretador de
JavaScript usado pelo navegador {\em Mozilla Firefox}.
Atualmente SpiderMonkey conta com um compilador base, entretando, como este se encontra
em fase de desenvolvimento e apresenta diversas instabilidades, preferimos implementar
nossa técnica apenas no interpretador de {\em bytecodes}.
Testamos essa implementação em um conjunto de 5 benchmarks, a saber:
SunSpider 1.0, V8 versão 6, Kraken 1.1, Richards 1.0 e Alexa.
SunSpider, V8 e Kraken são distribuídos no repositório da Fundação Mozilla.
Richards é um conjunto de programas extraídos de quatro páginas web -- yahoo,
google, facebook e tweeter -- por uma ferramenta criada por Richards
{\em et al.}~\cite{Richards10}.
Alexa são as 100 páginas mais visitadas da Internet, de acordo com o índice
Alexa~\footnote{\texttt{www.alexa.com}}.
Esses programas, combinados, dão-nos uma massa de testes de mais de meio
milhão de linhas de código.
Todos os experimentos mostrados nesse artigo foram realizados em um processador
Intel Core i5, com clock de 1.7 GHz, e 4 GB de memória RAM.
O sistema operacional usado nos testes foi Mac OS X 10.8 64-bit.
A versão de SpiderMonkey que utilizamos foi obtida do repositório de
desenvolvimento da Mozilla no dia 12 de abril de 2013.

\noindent
\textbf{Precisão do Preditor: }
A figura~\ref{fig:dynamicLoopData} mostra a precisão de nossa heurística.
Mostramos o número total de laços ($L$) que cada benchmark contém.
Estamos considerando qualquer tipo de laço natural, segundo a definição
de Appel e Palsberg~\cite[p.376]{Appel02}.
A coluna $P$ mostra o número de laços sobre os quais aplicamos nossa
heurística.
$P$ é bem menor que $L$ porque analisamos somente um laço
por interpretação de cada {\em script}.
Além disso, apenas laços de intervalo são analisados.
As demais colunas fornecem resultados relacionados à precisão de nossa
heurística.
A coluna $[N, N]$ contém o percentual de previsões exatas.
Uma previsão exata ocorre sempre que o valor predito pela nossa heurística é
exatamente o valor apurado pelo profiler.
A coluna $[N/2, N]$ mostra o percentual de previsões que ficaram na margem de
erro de 50\% do valor real apurado.
A coluna $[\sqrt{N}, N/2]$ denota o percentual de valores apurados que ficaram
entre a metade do valor previsto e a sua raiz quadrada.
A coluna $[1, \sqrt{N}]$ representa situações
em que o valor apurado foi menor que a raiz quadrada do valor previsto.
As colunas $[N, 2N]$, $[2N, N^2]$ e $[N^2, \infty]$ representam casos em que
o número de iterações do laço foi maior que o valor previsto.
Conforme podemos observar, nosso preditor de iterações acerta mais
de 60\% de suas estimativas.

\begin{figure}[t!]
\begin{center}
\begin{small}
\renewcommand{\arraystretch}{1.2}
\begin{tabular*}{\textwidth}{@{\extracolsep{\fill}}|l|r|r|r|r|r|r|r|r|r|} \hline
Benchmark      & $L$   & $P$   & $[1, \sqrt{N}]$ & $[\sqrt{N}, N/2]$  & $[N/2, N]$ & $[N, N]$  & $[N, 2N]$ & $[2N, N^2]$     & $[N^2, \infty]$ \\ \hline
SunSpider 1.0  & 244   & 138   & 2.17         & 1.45                & 0.72     & 76.81   & 2.17     & 5.80         & 13.04 \\ \hline
V8 v6          & 341   & 99    & 18.18        & 0.00                & 1.01     & 83.84   & 0.00     & 1.01         & 13.13 \\ \hline
Richards       & 176   & 59    & 6.78         & 0.00                & 0.00     & 67.80   & 0.00     & 0.00         & 28.81 \\ \hline
Kraken 1.1     & 165   & 88    & 7.95         & 2.27                & 0.00     & 70.45   & 0.00     & 1.14         & 21.59 \\ \hline
Alexa          & 5043  & 1057  & 14.47        & 2.18                & 1.89     & 60.26   & 3.12     & 3.03         & 32.17 \\ \hline
\end{tabular*}
\end{small}
\end{center}
\caption{Precisão do preditor estático.
L: número de laços encontrados no benchmark.
P: número de laços analisados.
$[l, u]$: percentagem de predições entre $l$ e $u$, sendo $N$ o número de
iterações do laço apuradas via profiling.}
\label{fig:dynamicLoopData}
\end{figure}

Nós implementamos o preditor também em LLVM, a fim de verificar se os
resultados observados em JavaScript se repetem em uma linguagem estaticamente
compilada.
A fim de realizar previsões e obter o número de iterações de cada laço, nós
utilizamos a instrumentação descrita na seção~\ref{sub:inst}.
A figura~\ref{fig:staticLoopData} mostra os resultados que encontramos
nesse experimento para os benchmarks C, que operam sobre números inteiros,
disponíveis em SPEC CPU 2006.
A fim de facilitar a realização desses experimentos instrumentamos somente o
primeiro laço encontrado em cada função.
Ainda assim, pudemos testar nossa técnica em mais de 50,000 laços
diferentes.
Conforme podemos observar, a taxa de acerto para programas C é
substancialmente melhor que a taxa de acerto para programas JavaScript.
Especulamos que tal resultado se verifique porque estamos usando programas
computacionalmente intensivos, cuja maior parte do tempo de execução acontece
no interior de laços.

\begin{figure}[t!]
\begin{center}
\renewcommand{\arraystretch}{1.2}
\begin{tabular*}{\textwidth}{@{\extracolsep{\fill}}|l|r|r|r|r|r|r|r|r|} \hline
Benchmark  & $[1, \sqrt{N}]$ & $[\sqrt{N}, N/2]$ & $[N/2, N]$ & $[N, N]$ & $[N, 2N]$ & $[2N, N^2]$ & $[N^2, \infty]$ & Total \\ \hline
bzip2      & 37.42  & 2.11   & 5.04   & 41.36  & 0.02   & 0      & 14.04 &   1.84E+05 \\ \hline
dealII     & 1.89   & 0.06   & 0.03   & 88.81  & 9.14   & 0.00   & 0.07  &   3.25E+07 \\ \hline
gobmk      & 94.84  & 3.91   & 0      & 1.22   & 0      & 0      & 0.04  &   5.91E+08 \\ \hline
lbm        & 0      & 99.51  & 0      & 0.39   & 0      & 0      & 0.10  &   1.51E+08 \\ \hline
libquantum & 0.17   & 0.00   & 0.01   & 98.27  & 0.01   & 0.01   & 1.53  &   2.09E+08 \\ \hline
mcf        & 43.92  & 4.74   & 5.14   & 35.05  & 0      & 0      & 11.14 &   1.60E+01 \\ \hline
milc       & 0.01   & 0      & 0      & 99.98  & 0.00   & 0.01   & 0.00  &   3.28E+04 \\ \hline
namd       & 0      & 21.73  & 55.20  & 23.05  & 0      & 0.01   & 0.01  &   1.46E+04 \\ \hline
omnetpp    & 9.80   & 0      & 11.76  & 68.63  & 7.84   & 1.96   & 0     &   0.00E+00 \\ \hline
sjeng      & 6.99   & 6.31   & 1.32   & 81.09  & 0.12   & 0.09   & 4.09  &   2.30E+03 \\ \hline
soplex     & 6.25   & 0      & 0      & 87.50  & 6.25   & 0      & 0     &   5.10E+01 \\ \hline
xalancbmk  & 43.99  & 0.73   & 0.08   & 44.97  & 0.07   & 0.07   & 10.09 &   7.36E+06 \\ \hline
\end{tabular*}
\end{center}
\caption{Precisão do preditor estático.
$[l, u]$: percentagem de predições entre $l$ e $u$, sendo $N$ o número de
iterações do laço apuradas via profiling.
\textbf{Total}: número total de laços analisados.}
\label{fig:staticLoopData}
\end{figure}

\noindent
\textbf{Melhoria de Desempenho: }
Atualmente, a equipe que desenvolve a {\em engine} SpiderMonkey está realizando
um grande esforço para produzir um ambiente de execução similar ao V8 da
Google.
Esse ambiente possui um compilador base, cuja meta é reduzir gradativamente a
necessecidade de um interpretador de {\em bytecodes}.
Assim, nessa versão de SpiderMonkey, um {\em script} é interpretado até que um
de seus laços itere 10 vezes.
Uma vez atingido este limiar o script sendo interpretado é traduzido pelo
compilador base.
Caso o programa se torne {\em quente}, ele será eventualmente re-compilado,
dessa vez por IonMonkey, um otimizador de código.
Se, durante o processo de execução, for observado algum evento que provoque
uma desotimização, o código executado é substituído pelo código genérico
produzido pelo compilador base.
Desse modo a execução do programa nunca retorna ao interpretador.
Por esse motivo, para executar os experimentos de ganho de desempenho, nós
utilizamos a versão estável do Firefox que não possui o compilador base.
Nessa versão, código é, ou interpretado, ou compilado por IonMonkey.
Para lidarmos com o compilador base, basta que implementemos nossa abordagem
no código que esse tradutor produz.
Uma vez que esse compilador ainda não é estável, optamos por não fazê-lo.

\begin{table}[t!]
\begin{minipage}[b]{.430\textwidth}
(a) SunSpider 1.0
\vspace*{2mm}

\begin{tabular}{|l|r|r|r|r|} \hline
Benchmark                   & $A0$  & $A0,I$  & $A1$  & $A1,I$    \\ \hline
3d-cube                     & 0   & 0   & 0   & 0  \\ \hline
3d-morph                    & 13  & 14  & 30  & 27  \\ \hline
3d-raytrace                 & 0   & 0   & 0   & 0  \\ \hline
access-binary-trees         & 5   & 5   & 8   & 3  \\ \hline
access-fannkuch             & -6  & 0   & 0   & -3  \\ \hline
access-nbody                & 0   & 0   & 0   & 0  \\ \hline
access-nsieve               & 6   & 7   & 9   & 8  \\ \hline
bitops-3bit                 & 0   & 0   & 0   & 3  \\ \hline
bitops-bits-in-byte         & 0   & 0   & -11 & -8  \\ \hline
bitops-bitwise-and          & 14  & 14  & 16  & 16  \\ \hline
bitops-nsieve-bits          & 16  & 17  & 19  & 15  \\ \hline
controlflow-recursive       & 0   & 0   & 0   & -2  \\ \hline
crypto-aes                  & 0   & 0   & 0   & -3  \\ \hline
crypto-md5                  & 75  & 75  & 71  & 73  \\ \hline
crypto-sha1                 & 63  & 65  & 57  & 62  \\ \hline
date-format-tofte           & 0   & 0   & 4   & 2  \\ \hline
date-format-xparb           & 11  & 11  & 13  & 12  \\ \hline
math-cordic                 & 15  & 16  & 14  & 15  \\ \hline
math-partial-sums           & 53  & 52  & 54  & 55  \\ \hline
math-spectral-norm          & 0   & 0   & 0   & 0  \\ \hline
regexp-dna                  & 0   & 0   & 0   & 0  \\ \hline
string-base64               & 88  & 91  & 89  & 88  \\ \hline
string-fasta                & 8   & 10  & 8   & 9  \\ \hline
string-tagcloud             & 0   & 0   & 4   & 3  \\ \hline
string-unpack-code          & 0   & 0   & 8   & 7  \\ \hline
string-validate-input       & 9   & 11  & 13  & 9  \\ \hline
$Total$                     & 9   & 8   & 11  & 10  \\ \hline
\end{tabular}
\end{minipage}
\qquad
\begin{minipage}[b]{.50\textwidth}
(b) Kraken 1.1
\vspace*{2mm} 

\begin{tabular}{|l|r|r|r|r|} \hline
Benchmark                           & $A0$  & $A0,I$  & $A1$  & $A1,I$    \\ \hline 
ai-astar                            & 0  & 0  & 0  & 1  \\ \hline
audio-beat-detection                & -1 & -2 & -5 & -3  \\ \hline
audio-dft                           & 3  & 2  & 0  & 2  \\ \hline
audio-fft                           & 3  & 2  & 0  & 3  \\ \hline
audio-oscillator                    & 2  & 2  & 2  & 3  \\ \hline
imaging-gaussian-blur               & 0  & 0  & 4  & 2  \\ \hline
imaging-darkroom                    & 0  & 1  & 0  & 0  \\ \hline
imaging-desaturate                  & 0  & 0  & 0  & 0  \\ \hline
json-parse-financial                & 3  & 0  & 3  & 2  \\ \hline
json-stringify-tinderbox            & 6  & 4  & 2  & 3  \\ \hline
crypto-aes                          & 5  & 4  & -2 & -2  \\ \hline
crypto-ccm                          & 0  & 0  & -2 & 0  \\ \hline
crypto-pbkdf2                       & 0  & 0  & 0  & 0  \\ \hline
crypto-sha256-it.                   & 3  & 2  & 0  & 1  \\ \hline
$Total$                             & 2  & 1  & 0  & 0  \\ \hline
\end{tabular}
\end{minipage}
\vspace*{2mm} 
\caption{{\em Speedup} percentual alcançado por nossa técnica.
\textbf{A0:} política arrojada que invoca o compilador JIT se o
primeiro laço for considerado quente.
\textbf{A1:} política prudente, que invoca o compilador JIT se
o laço aninhado for considerado quente.
\textbf{I:} compilação com integração de procedimentos.
A margem de erro é insignificante.}
\label{table:speedups}
\end{table}

A tabela~\ref{table:speedups} mostra os ganhos de velocidade obtidos ao se
executar os benchmarks SunSpider 1.0, desenvolvido pela empresa Apple, e Kraken
1.1, desenvolvido pela Fundação Mozilla.
Apesar de sua simplicidade, nosso preditor consegue ganhos de velocidade
superiores a 50\% em vários casos de teste.
Nos outros benchmarks, isto é, em V8 versão 6 e Richards 1.0 não foram
observados ganhos significativos de desempenho.
Especulamos que não obtivemos ganho nesses dois casos porque esses benchmarks
executam durante muito tempo, e pequenas variações no momento de invocação do
compilador deixam de ser significativas.
A abordagem que utilizamos nestes experimentos foi: sempre que um {\em script}
se torna {\em quente} o suficiente para ser otimizado, ele é 
imediatamente entregue ao compilador IonMonkey.
O limiar usado para determinar se um {\em script} é quente ou não são
1,000 iterações de laços, ou invocações.
Dessa forma, em programas como aqueles encontrados nos benchmarks V8 e
Richards, em que testes são executados por longos períodos, o tempo gasto no
interpretador -- essas
1,000 iterações -- é insignificante em relação ao tempo gasto executando-se
código otimizado.
A tabela~\ref{table:speedups} compara três diferentes políticas de
invocação do compilador JIT.
As políticas arrojada e prudente foram descritas na seção~\ref{sub:pol}.
A política \textbf{I} representa a compilação com integração de
procedimentos: sempre que um laço é predito como quente, todos as funções
invocadas em seu interior são imediatamente compiladas, e o código das
menores é aninhado ao código do laço.

%mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm
\section{Trabalhos Relacionados}
\label{sec:rel}

O problema de separar um programa em partes quentes e frias tem sido um dos
mais importantes desafios enfrentados por quem se propõe a implementar um
compilador Just-in-Time~\cite{Aycock03}.
Conforme discutimos na seção~\ref{sec:bkg}, a principal técnica adotada para
enfrentar tal desafio é a compilação baseada em limiares.
O trabalho referência nessa área foi publicado por Duesterwald {\em et al.}
no ano de 2000~\cite{Duesterwald00}.
Os autores daquele trabalho propuseram a realização de {\em profiling}
durante a interpretação dos programas, usando métodos de baixo custo
computacional.
O {\em profiler}, nesse caso, resume-se a um simples contador associado aos
cabeçalhos de laços, incrementado a cada uma de suas iterações.
Atingindo o contador um certo limiar, o compilador just-in-time é
invocado, e código nativo é produzido para o programa instrumentado.
Essa abordagem foi usada com grande sucesso no otimizador dinâmico
{\em Dynamo}~\cite{Bala00}.

Os trabalhos que se seguiram ao artigo seminal de Dusterwald {\em et al.}
procuraram diminuir o custo do {\em profiler}, ou torná-lo mais
preciso.
Na primeira linha de pesquisa, citam-se trabalhos em {\em profiling} por
amostragem, e via contadores implementados em {\em hardware}.
A amostragem consiste na inspeção periódica do valor do contador de
programa~\cite{Chen03}.
Funções que tiveram suas instruções amostradas mais frequentemente são
consideradas quentes, e portanto traduzidas para código nativo.
Outra forma de diminuir o custo incorrido pelo {\em profiler} é via
contadores implementados em {\em hardware}~\cite{Merten00}.
Esses contadores podem armazenar, por exemplo, a frequência das últimas
instruções de desvio vistas.
Quando alguma dessas instruções atinge um limiar específico, interrupções de
{\em hardware} se encarregam de chamar o compilador just-in-time.

Em termos de precisão, o grupo de Youfeng Wu avançou as idéias inicialmente
propostas por Dusterwald {\em et al.} em várias direções.
Youfeng {\em et al.} mostraram que em muitos casos o comportamento inicialmente
observado acerca de um laço não se repete ao longo da execução do
programa~\cite{Wu04a,Wu04b}.
A partir dessa observação, eles propuseram diversas heurísticas que procuram
adaptar-se às chamadas {\em mudanças de fase} do programa.
Em outras palavras, um programa possui diversas fases: algumas
computacionalmente intensivas, outras mais iterativas.
Youfeng {\em et al.} observaram que o número de iterações de um laço varia
de acordo com a fase em que se encontra o programa.
Também partindo dessa observação, Inoue {\em et al.}~\cite{Inoue12} propuseram
uma série de otimizações que podem ser aplicadas durante diferentes momentos
da execução de um programa.
Essa é, em seus fundamentos, a idéia que norteia o projeto do navegador
Mozilla firefox: a representação do programa evolui para formas cada vez mais
eficientes, conforme o tempo de execução da aplicação alvo se alonga.

Existem outras formas, diferentes das técnicas baseadas em limiares, que
podem ser usadas para determinar quando o compilador just-in-time deve ser
invocado.
Dentre esses métodos, vale mencionar o trabalho ainda não publicado de Rompf
{\em et al.}, no contexto de
Scala~\footnote{\texttt{https://github.com/TiarkRompf/lancet}}.
Esse grupo projetou Lancet, um compilador just-in-time que pode
ser invocado pelo programador via construtos de alto nível.
A sintaxe dessas construções é definida em uma biblioteca de Scala, e
permite que o programador indique quais funções devem ser imediatamente
compiladas.
Lancet permite também a especialização parcial de funções com base nos
valores de alguns de seus parâmetros, de forma similar à estratégia
proposta por Costa {\em et al.}~\cite{Alves12,Costa13}.

Tendo discorrido sobre alguns trabalhos relacionados à previsão de
código quente, nós acreditamos que a nossa abordagem é substancialmente
diferente.
Nenhum dos trabalhos anteriormente citados utilizou nossa técnica de inferir
o tamanho de um laço em tempo de execução via a leitura de sua condição de
controle.
Entretanto, testes similares aos nossos foram usados por Jiang
{\em et al.}~\cite{Jiang10} para estabelecer correlações estatísticas
entre laços de um programa.
Esses testes também foram propostos por Sherwood {\em et al.} como um
mecanismo, que deveria ser implementado a nível de {\em hardware}, para prever
que laços terminam~\cite{Sherwood00}.
Contudo, em nenhum desses trabalhos o resultado dos testes foi usado para
invocar um compilador just-in-time.
Números relacionados à precisão desses testes também não foram fornecidos.

%mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm
\section{Considerações Finais}
\label{sec:con}

Esse artigo descreveu uma nova abordagem para invocar um compilador
just-in-time, baseada na predição dinâmica do número de iterações de laços.
Implementamos nossa técnica em dois ambientes de execução: SpiderMonkey, usado
no navegador Mozilla Firefox, e LLVM, usado para compilar programas C.
Em ambos os casos, nossa técnica acerta mais de 60\% do número de
iterações de laços.
Uma de nossas prioridades atualmente é implementar a abordagem aqui descrita no
compilador base usado em SpiderMonkey, a fim de tornar nossa técnica mais
compatível com a atual versão do navegador Firefox.
Estamos trabalhando para enviar nossa implementação à Fundação Mozilla, para que
ela possa fazer parte das próximas versões do navegador Firefox.
Informações adicionais sobre este trabalho, incluindo as instruções 
necessárias para reproduzir nossos experimentos estão disponíveis no endereço:
\texttt{https://code.google.com/p/js-loop-inference}.


\bibliographystyle{plain}
\bibliography{references}

\end{document}
